package com.chanzany.leetCode;

//2是第一个素数，3是第二个素数，则第100001个素数是多少
//筛法：
// 2*,3,4,5,6.......18 将2的倍数筛出
// 2,3*,5,7,9.......17 将3的倍数筛出
// 2,3,5*,7,9.......17 将5的倍数筛出
//根据算术基本定理，每一个比1大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积(合数)，最小的质数是2
/*在这里，筛选法是一个两层的for循环，两个关键点
 *1、思路是，i * k 如果还在 N 之内，即该数可以被i*k整除，不满足素数，筛掉，标1
 *2、i与k的循环条件，ik均从2开始循环，那么试想，i*k在满足<N时，他们的最大是多少呢
 *   明显，i=2；i<N/2  i最大为 N/2
 *   相应的，i*k<N, k=2;k<N/i
 *Ps. ik为什么从2开始？因为若ik为1的话，乘得的数可能为素数，例如1*1=1；1*3=3。。。
 *   ik从2开始的话，第一个判断的数为4，而2、3正好都为素数，所以置之不理即可。
 *   对于1不计入素数，所以本题的循环大多从2 开始，直接略过1。
 **/
public class The_n_PrimeNumber {
    public static void f1(){
        int N = 1000*1000*10;//从1~N的所有整数开辟了一个数组空间
        int x = 100002;
        byte[] a = new byte[N]; //标记数组，判断对应的下标数是否为素数，为则0不为则1
        for (int i = 2; i < N/2; i++) { //假设 k*i<N,当k=2,i<N/2
            if (a[i]==1) continue; //合数没有资格参加筛选
            for (int k = 2; k <=N/i; k++) { // k*i<N
                if (i*k<N) a[i*k]=1; //(i*k)<N既可以被i整除也可以被k整除
            }
        }
        int m = 0;
        for (int i = 2; i < N; i++) {
            if (a[i]==0){ //每遇到一个素数counter+1
                m++;
                if (m==x) System.out.print("第"+x+"个素数为"+i+" ");
            }
        }
        System.out.println("2~N内总共有"+m+"个素数");
    }
    public static void main(String[] args) {
        f1();
    }
}
